
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1159. -- [CTSC2005]孤独的牧羊女
dalarna
</title><center><h2>1159: [CTSC2005]孤独的牧羊女
dalarna
</h2><span class=green>Time Limit: </span>100 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>162 MB<br><span class=green>Submit: </span>8&nbsp;&nbsp;<span class=green>Solved: </span>0<br>[<a href='submitpage.php?id=1159'>Submit</a>][<a href='problemstatus.php?id=1159'>Status</a>][<a href='bbs.php?id=1159'>Discuss</a>]</center><h2>Description</h2><div class=content>在瑞典的达拉纳洲有一座高山。山上有一个小屋，里面住着一位牧羊女。每天清晨，隔壁的山头会传来一阵悠扬的长笛声，而牧羊女则会站在屋里用自己的歌声回应。
小屋的俯视图是一个有n个顶点的简单多边形，每一面墙可以反射声音，但是由于不可避免的能量损失，最多只能反射k次（k=0表示不能反射声音）。墙面非常光滑，因此声音的反射遵循反射角等于入射角，如图1。墙角不能反射声音，而每面墙的其他部分——即使离墙角很近——都可以反射声音。
<img border="0" src="images/1159_1.jpg">
图1. 声音的反射

突然有一天，牧羊女问自己：在小屋的哪些地方能听到她的歌声？假设所有听众都在屋里靠墙而坐，那么歌声能到达的墙一共有多长？
图2的四幅示意图分别画出了初始情况和声音经过0、1、2次反射后到达的区域。灰色部分表示能听到歌声的部分，黑点表示牧羊女的位置。本题所求即灰色部分在多边形边界上的总长度。
<img border="0" src="images/1159_2.jpg">
              (a) 初始情况                                 (b)声音发出后未经反射
<img border="0" src="images/1159_3.jpg">  
              (c) 声音1次反射                                  (d) 声音2次反射
图2. 能听到歌声的区域

</div><h2>Input</h2><div class=content>第一行包含4个整数n，k，x，y分别表示小屋的墙角数、最多反射的次数以及牧羊女的坐标（牧羊女所在位置保证在屋内且至少离墙1个单位）。以下n行每行两个整数x, y，表示第i个墙角的坐标。墙角按照顺时针或逆时针排列。

</div><h2>Output</h2><div class=content>输出文件仅包含一个实数L，表示能听到歌声的墙的总长度。保留两位小数。

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>【样例输入1】<br />
5 0 100 135<br />
20 200<br />
200 100<br />
300 125<br />
40 10<br />
100 100<br />
<br />
<br />
【样例输入2】<br />
8 1 25 15<br />
0 0<br />
0 20<br />
30 20<br />
30 0<br />
20 0<br />
20 10<br />
10 10<br />
10 0<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>【样例输出1】<br />
469.86<br />
<br />
【样例输出2】<br />
106.67<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p>【评分方法】<br />
选手输出和参考输出差的绝对值不大于0.02时该测试点满分，相差超过0.02但不超过1时该测试点得50%的分数。在样例1中，答案为469.84和469.88都能拿满分，468.86和470.86都能拿50%的分数。<br />
<br />
【约定】<br />
3<=n<=50，0<=k<=5，所有坐标为绝对值不超过1000的整数<br />
50%的数据满足k<=1<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1159'>Submit</a>][<a href='problemstatus.php?id=1159'>Status</a>][<a href='bbs.php?id=1159'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
